Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Звіт
про виконання лабораторної роботи N3
з курсу “Алгоритмічні основи криптології”
на тему: “Метод Ньютона для розв’язування
систем нелінійних рівнянь ”
Львів – 2004
Мета роботи: ознайомитися з найпоширенішим ітераційним методом розв’язування систем нелінійних рівнянь – методом Ньютона.
Завдання: написати програму на мові програмування Сі яка б розв’язувала систему нелінійних рівнянь модифікованим методом Ньютона, реалізувати обертання матриць методом Гауса, а обчислення похідних методом кінцевих різниць.
x1 = x12 – x22 – 0.1 ,
x2 = 2x1x2 + 0.1 ,
x10 = 0,
x20 = 0,
Блок – схема алгоритму роботи програми
Текст програми:
#include<stdio.h>
#include<math.h>
#include<conio.h>
#define n 2
#define er 0.00001
#define h 10e-9
static float JacP[n+2][n+2],Jacobi[n+2][n+2];
/* Fynkcija obertannja matruci met. Gausa*/
Gaus(float a[n+2][n+2])
{
int i,k,d,f;
float aa[n+2][n+2],b[n+1];
float s=0;
for(f=1;f<=n;f++)
{
for (i=1;i<=n;i++)
{
if (f==i)
b[i]=1;
else b[i]=0;
a[i][n+1]=((-1)*b[i]);
}
for(d=1;d<=(n-1);d++)
for(i=d+1;i<=n;i++)
for(k=d+1;k<=(n+1);k++)
{
aa[d][k]=((-1)*a[d][k]/a[d][d]);
a[i][k]=(a[i][d]*aa[d][k])+a[i][k];
}
Jacobi[n][f]=(-1)*a[n][n+1]/a[n][n];
for(i=n-1;i>=1;i--)
{
for (k=i+1;k<=n;k++)
s+=aa[i][k]*JacP[n][f];
Jacobi[n-1][f]=aa[i][n+1]+s;
s=0;
}
}
return(Jacobi[n+2][n+2]);
}
/*Fynkcija vuznachennja znachen' fynkcii*/
float func(float x1,float x2,int i)
{
if (i==1)
return (x1-(x1*x1)+(x2*x2)+0.1);
else
return (x2-(2*x1*x2)-0.1);
}
/*Vukonannja samoi programu*/
void main(void)
{
int i,j;
float x[n+2];
int m;
float Max,x1,y1,s1;
x[1]=0;
x[2]=0;
do
{
x1=x[1];
y1=x[2];
/*Vuznachennja znachennja poxidnux met. kincevux riznuc'*/
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
if (j==1)
JacP[i][j] = (func(x[j]+h,x[j+1],i)-func(x[j],x[j+1],i))/h;
else
JacP[i][j] = (func(x[1],x[j]+h,i)-func(x[1],x[j],i))/h;
}
/*Vukonannja funkcii Gaus*/
Gaus(JacP);
for (i=1;i<=n;i++)
{
s1=0;
for (j=1;j<=n;j++)
{
if (j==1)
Jacobi[i][j]*=func(x[j],x[j+1],i);
else Jacobi[i][j]*=func(x[j-1],x[j],i);
s1+=Jacobi[i][j];
}
if (i==1)
x[i]=x1-s1;
else
x[i]=y1-s1;
}
/*Perevirka poxubku*/
Max=fabs((x[1]-x1)/x[1]);
if (fabs((x[2]-y1)/x[2])>Max)
Max=fabs((x[2]-y1)/x[2]);
if(Max<er)
{
m=1;break;
}
else m=0;
}
while (m!=1);
for(i=1;i<=n;i++)
{
printf ("\nx[%d]=%2.5f",i,x[i]);
}
printf ("\n f1 = (x1-(x1*x1)+(x2*x2)+0.1) = %f" , (x[1]-(x[1]*x[1])+(x[2]*x[2])+0.1));
printf ("\n f2 = (x2-(2*x1*x2)-0.1) = %f" , (x[2]-(2*x[1]*x[2])-0.1));
Результат виконання програми:
Висновок:
Розв’язання систем нелінійних алгебраїчних рівнянь методом Ньютона можна досить легко реалізувати на ЕОМ за допомогою програми в середовищі Сі. Основна перевага модифікованого методу Ньютона полягає в тому, що при використанні цього методу якобіан замінюють правильно підібраною матрицею, яку зберігають сталою протягом деякого числа ітерацій, а потім на певній ітерації її заново обчислюють і присвоюють знайдене значення якобіану. Це дозволяє значно зекономити машинний час виконання програми. Розв’язання таких систем на ЕОМ є дуже актуальним, оскільки цей процес є набагато легшим та короткотривалішим ніж розв’язання систем нелінійних рівнянь вручну.
